{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Substrings with Only One Distinct Letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countLetters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计只含单一字母的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code>，返回 <em>只含 <strong>单一字母</strong> 的子串个数</em> 。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入： </strong>s = \"aaaba\"\n",
    "<strong>输出： </strong>8\n",
    "<strong>解释： </strong>只含单一字母的子串分别是 \"aaa\"， \"aa\"， \"a\"， \"b\"。\n",
    "\"aaa\" 出现 1 次。\n",
    "\"aa\" 出现 2 次。\n",
    "\"a\" 出现 4 次。\n",
    "\"b\" 出现 1 次。\n",
    "所以答案是 1 + 2 + 4 + 1 = 8。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入： </strong>s = \"aaaaaaaaaa\"\n",
    "<strong>输出： </strong>55\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-substrings-with-only-one-distinct-letter](https://leetcode.cn/problems/count-substrings-with-only-one-distinct-letter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-substrings-with-only-one-distinct-letter](https://leetcode.cn/problems/count-substrings-with-only-one-distinct-letter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaaba\"', '\"aaaaaaaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        res = 0\n",
    "        plus = 1\n",
    "        pre = 0\n",
    "        for i in s:\n",
    "            if pre == i:\n",
    "                plus += 1\n",
    "                res += plus\n",
    "            \n",
    "            else:\n",
    "                plus = 1\n",
    "                res += plus\n",
    "\n",
    "            pre = i\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        num_list = [1]\n",
    "        last = s[0]\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==last:\n",
    "                num_list[-1]+=1\n",
    "            else:\n",
    "                num_list.append(1)\n",
    "            last = s[i]\n",
    "        \n",
    "        num = 0\n",
    "        for i in num_list:\n",
    "            num+= self.count(i)\n",
    "        return int(num)\n",
    "    \n",
    "    def count(self, i:int):\n",
    "        if i==1:\n",
    "            return 1\n",
    "        else:\n",
    "            return (i)*(i+1)/2\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        total = 0\n",
    "        s += '.'\n",
    "        idx = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i]!=s[i-1]:\n",
    "                total += (i-idx)*(i-idx+1)//2\n",
    "                idx = i  \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        res = 0\n",
    "        plus = 1\n",
    "        pre = 0\n",
    "        for i in s:\n",
    "            if pre == i:\n",
    "                plus += 1\n",
    "                res += plus\n",
    "            \n",
    "            else:\n",
    "                plus = 1\n",
    "                res += plus\n",
    "\n",
    "            pre = i\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "            i, l, count = 0, len(s), 0\n",
    "        \n",
    "            while i < l:   \n",
    "                sc = 0\n",
    "                while i + 1 < l and s[i] == s[i + 1]:\n",
    "                    sc += 1\n",
    "                    i += 1\n",
    "                count += (2 + sc) * (sc + 1) // 2\n",
    "                i += 1\n",
    "                \n",
    "            return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = left = 0\n",
    "        while left < n:\n",
    "            right = left\n",
    "            while right < n and s[right] == s[left]:\n",
    "                ans += right - left + 1\n",
    "                right += 1\n",
    "            left = right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        total=0\n",
    "        idx=0\n",
    "        #加个哨兵字符\n",
    "        s=s+\".\"\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]!=s[i-1]:\n",
    "                total+=(i-idx)*(i-idx+1)//2\n",
    "                idx=i\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        n = len(s) \n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i]!=s[i-1]:\n",
    "                ans += (cur+1)*cur//2\n",
    "                cur = 1\n",
    "            else:\n",
    "                cur += 1\n",
    "        ans += (cur+1)*cur//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        ans = []\n",
    "        cur = s[0]\n",
    "        le = 1\n",
    "        for ch in s[1:]:\n",
    "            if ch == cur:\n",
    "                le += 1\n",
    "            else:\n",
    "                ans.append((le+1)*le/2)\n",
    "                le = 1\n",
    "                cur = ch\n",
    "        ans.append((le+1)*le/2)\n",
    "        return int(sum(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, l = 0, 0\n",
    "        cnt = Counter()\n",
    "        for r, c in enumerate(s):\n",
    "            cnt[c] += 1\n",
    "            while len(cnt) > 1:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0: del cnt[s[l]]\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        # for i in range(n):\n",
    "        #     j = i\n",
    "        #     while j < n and s[i] == s[j]:\n",
    "        #         j += 1\n",
    "        #     ans += j - i\n",
    "        left = 0\n",
    "        while left < n:\n",
    "            right = left\n",
    "            while right < n and s[right] == s[left]:\n",
    "                ans += right - left + 1\n",
    "                right += 1\n",
    "            left = right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "\n",
    "        r,l=0,0\n",
    "        ans=0\n",
    "\n",
    "        while r<len(s):\n",
    "            if s[r]==s[l]:\n",
    "                ans+=1+r-l\n",
    "            else:\n",
    "                l=r\n",
    "                ans+=1\n",
    "            r+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        temp = 1\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                temp+=1\n",
    "            else:\n",
    "                ans +=  (temp+1)*temp//2\n",
    "                temp = 1\n",
    "        ans+= (temp+1)*temp//2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        slow,fast=0,0\n",
    "        amount=0\n",
    "        sub=0\n",
    "        while fast<len(s):\n",
    "            while s[slow]==s[fast]:\n",
    "                fast+=1\n",
    "                if fast==len(s):\n",
    "                    break\n",
    "            sub=fast-slow\n",
    "            sum1=sub*(sub+1)//2\n",
    "            amount=amount+sum1\n",
    "            slow=fast\n",
    "        return amount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        ans = pre = 1\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            if s[i] == s[i-1]:\n",
    "                pre += 1\n",
    "                ans += pre\n",
    "            else:\n",
    "                ans += 1\n",
    "                pre = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        if len(s)<2:\n",
    "            return len(s)\n",
    "        prev = 1\n",
    "        res = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]==s[i-1]:\n",
    "                prev+=1\n",
    "            else:\n",
    "                prev = 1\n",
    "            res+=prev\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        total=0\n",
    "        idx=0\n",
    "        #加个哨兵字符\n",
    "        s=s+\".\"\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]!=s[i-1]:\n",
    "                total+=(i-idx)*(i-idx+1)//2\n",
    "                idx=i\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        def countletter(length:int)-> int:\n",
    "            if length == 1:\n",
    "                return 1\n",
    "            else:\n",
    "                return int(length * (length+1)/2)\n",
    "        \n",
    "        r = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            print(i)\n",
    "            for j in range(i,len(s)+1):\n",
    "                if j == len(s):\n",
    "                    r += countletter(len(s[i:j]))\n",
    "                    i = j-1\n",
    "                elif s[i] == s[j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    r += countletter(len(s[i:j]))\n",
    "                    i = j-1\n",
    "                    break\n",
    "            i += 1\n",
    "        return r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            cur = 1\n",
    "            res += cur\n",
    "            while i + 1 < n and s[i] == s[i+1]:\n",
    "                cur += 1\n",
    "                res += cur\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        i = 0\n",
    "        ret = 0\n",
    "        for j, c in enumerate(s):\n",
    "            if c != s[i]:\n",
    "                i = j\n",
    "            ret += j - i + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        ans = []\n",
    "        cur = s[0]\n",
    "        le = 1\n",
    "        for ch in s[1:]:\n",
    "            if ch == cur:\n",
    "                le += 1\n",
    "            else:\n",
    "                ans.append((le+1)*le/2)\n",
    "                le = 1\n",
    "                cur = ch\n",
    "        ans.append((le+1)*le/2)\n",
    "        print(ans)\n",
    "        return int(sum(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        return sum((i.end() - i.start()) * (i.end() - i.start() + 1)//2 for i in re.finditer(r\"(\\w)\\1*\", s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        temp = 1\n",
    "        s = s + '!'\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i + 1] != s[i]:\n",
    "                ans += temp\n",
    "                temp = 1\n",
    "            else:\n",
    "                ans += temp\n",
    "                temp += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countLetters(self, s: str) -> int:\n",
    "#         # slow=0\n",
    "#         # fast=0\n",
    "#         # n=len(s)   \n",
    "#         # count=0\n",
    "#         # sublenth=0\n",
    "#         # while fast<n:\n",
    "#         #     while s[slow]==s[fast]:\n",
    "#         #         fast+=1\n",
    "#         #         if fast==n:\n",
    "#         #             break\n",
    "#         #     sublenth=fast-slow\n",
    "#         #     count=count+sublenth*(sublenth+1)//2\n",
    "#         #     slow=fast\n",
    "#         # return count\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        slow=0\n",
    "        fast=0\n",
    "        amount=0\n",
    "        sub=0\n",
    "        while fast<len(s):\n",
    "            while s[slow]==s[fast]:\n",
    "                fast+=1\n",
    "                if fast==len(s):\n",
    "                    break\n",
    "          \n",
    "            sub=fast-slow\n",
    "            count1=sub*(sub+1)//2\n",
    "            amount=amount+count1\n",
    "            slow=fast\n",
    "        return amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        i = 0\n",
    "        c = \"\"\n",
    "        ret = 0\n",
    "        for j, char in enumerate(s):\n",
    "            if char != c:\n",
    "                c = char\n",
    "                i = j\n",
    "            ret += j - i + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        left = 0 \n",
    "        right =0\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        while right<n:\n",
    "            if s[right]!=s[left]:\n",
    "                res+=(right-left)*(right-left+1)//2\n",
    "                print(left,right,res)\n",
    "                left = right\n",
    "            right += 1\n",
    "        res+=(right-left)*(right-left+1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        d = collections.Counter(s)\n",
    "        l = len(s)\n",
    "        ans = 0\n",
    "        for i in d.keys():\n",
    "            for j in range(1,d[i]+1):\n",
    "                pipei = i*j \n",
    "                t = 0\n",
    "                while t<l:\n",
    "                    idx = s.find(pipei,t)\n",
    "                    if idx == -1:\n",
    "                        break\n",
    "                    ans+=1\n",
    "                    t = idx+1          \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        series_length = []\n",
    "        sub_series_count = 0\n",
    "        last_index = 0\n",
    "        last_char = s[0]\n",
    "        for cur_index, cur_char in enumerate(s):\n",
    "            if cur_char == last_char:\n",
    "                continue\n",
    "            series_length.append(cur_index - last_index)\n",
    "            last_index = cur_index\n",
    "            last_char = cur_char\n",
    "        series_length.append(len(s) - last_index)\n",
    "\n",
    "        print(series_length)\n",
    "\n",
    "        for n in series_length:\n",
    "            sub_series_count += (n ** 2 - n) // 2 + n\n",
    "\n",
    "        return sub_series_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        count = 1\n",
    "        for i in range(1,n):\n",
    "            if s[i] == s[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                res += count * (count+1) // 2\n",
    "                count = 1\n",
    "        res += count * (count+1) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        num = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        n = len(s)\n",
    "        c_pre = []\n",
    "        c_pre.append(s[0])\n",
    "        fac = 0\n",
    "        while j < n:\n",
    "            if s[j] in c_pre:\n",
    "                fac += (j - i + 1)\n",
    "                j += 1\n",
    "            else:\n",
    "                c_pre[0] = s[j]\n",
    "                num += fac\n",
    "                fac = 0\n",
    "                i = j\n",
    "        num += fac\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        def count(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            return n+count(n-1)\n",
    "        \n",
    "        i = 0\n",
    "        pre = s[0]\n",
    "        res = 0\n",
    "        while i < len(s):\n",
    "            cur = 0\n",
    "            while i < len(s) and s[i] == pre:\n",
    "                i += 1\n",
    "                cur += 1\n",
    "            # print(cur)\n",
    "            if i == len(s):\n",
    "                return res + count(cur)\n",
    "            res += count(cur)\n",
    "            pre = s[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import groupby\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        def f(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n == 2:\n",
    "                return 3\n",
    "            return f(n-1) + n\n",
    "        \n",
    "        ret = 0\n",
    "\n",
    "        for k, g in groupby(s):\n",
    "            ret += f(len(list(g)))\n",
    "        return ret\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import groupby\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def countLetters(self, s: str) -> int:\n",
    "        @lru_cache\n",
    "        def f(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n == 2:\n",
    "                return 3\n",
    "            return f(n-1) + n\n",
    "        \n",
    "        ret = 0\n",
    "\n",
    "        for k, g in groupby(s):\n",
    "            ret += f(len(list(g)))\n",
    "        return ret\n",
    "\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
